package huawei;
/*
* @Author: wanghongfucoder
* @Date:   2017-06-27 14:35:44
* @Last Modified by:   wanghongfucoder
* @Last Modified time: 2017-06-27 14:54:27
*/

public class Lcs {
	public static void main(String[] args) {
		String str1="1A2C3D4B56";
        String str2="B1D23CA45B6A";
        int[][] result=new int[str1.length()][str2.length()];
        boolean flag=false;
        for (int i=0; i<str1.length(); i++) {
        	if (str2.charAt(0)==str1.charAt(i) || flag) {
        		result[i][0]=1;
        		flag=true;
        	}
        }
        flag=false;
        for (int i=0; i<str2.length(); i++) {
        	if (str1.charAt(0)==str2.charAt(i) || flag) {
        		result[0][i]=1;
        		flag=true;
        	}
        }
        int ans=0;
        for (int i=1; i<str1.length(); i++) {
        	int max=0;
        	for (int j=1; j<str2.length(); j++) {
        		max=Math.max(result[i][j-1], result[i-1][j]);
        		if (str1.charAt(i)==str2.charAt(j)) {
        			max=Math.max(max, result[i-1][j-1]+1);
        		}
        		result[i][j]=max;
        		if (max>ans) {
        			ans=max;
        		}
        	}
        }
        System.out.println(ans);
	}
}